package codeTop;

import java.util.Arrays;
import java.util.Stack;

public class q739 {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        res[n-1] = 0;
        for (int i = n-2; i >=0 ; i--) {
            int idx = i+1;
            while (temperatures[i]>=temperatures[idx]&&res[idx]!=0){
                res[i]+=res[idx];
                idx += res[idx];
            }
            if (temperatures[i]<temperatures[idx]){
                res[i]++;
            }else {
                res[i] = 0;
            }
        }
        return res;
    }
    public int[] dailyTemperatures1(int[] temperatures) {
        int n = temperatures.length;
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            while ((!stack.isEmpty())&&temperatures[stack.peek()]<temperatures[i]){
                int pop = stack.pop();
                res[pop] = i-pop;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            res[stack.pop()] = 0;
        }
        return res;
    }

    public static void main(String[] args) {
        q739 q = new q739();
        System.out.println(Arrays.toString(q.dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73})));
    }
}
